package cn.dlc.com.graph;

import cn.dlc.com.stack.Stack;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/30 21:58
 * @desc 使用深度优先序列化顶点
 */
@Data
public class DepthFirstOrder {

    // :索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    // :使用栈存储顶点序列
    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph digraph){
        this.marked = new boolean[digraph.getV()];
        // 初始化这个栈
        reversePost = new Stack<>();

        // 遍历所有的顶点
        for (int i = 0; i < digraph.getV(); i++) {
            if(!marked[i]){
                dfs(digraph, i);
            }

        }
    }

    // 深度遍历的方式获取顶点
    private void dfs(Digraph digraph, int v) {
        // 当前顶点已经被遍历
        this.marked[v] = true;

        for (Integer w : digraph.adj(v)) {
            if(!marked[w]) {
                dfs(digraph, w);
            }
        }
        // 把这个顶点方进去
        reversePost.push(v);
    }

    // 获取顶点序列
    public Stack<Integer> reversePost() {
        return this.getReversePost();
    }
}
